The present invention relates to three-dimensional displays, and, more particularly, to generation of three-dimensional displays from two-dimensional cross sections.
Information about a three-dimensional object is frequently only available in the form of a series of parallel two-dimensional cross sections of the object, and three-dimensional displays must be reconstructed from such cross sections. For example, CAT scans of a human brain provide a series of cross sections which can be stacked to yield an accurate three-dimensional display of the brain if the spacing between successive cross sections is small enough. Likewise, seismic exploration frequently acquires data along parallel surface lines and thereby generates a series of two-dimensional sectional images of the earth's subsurface formations. Similarly, analyses of the microstructure of rocks often depends upon two-dimensional cross sections. Some bulk rock properties such as porosity and grain size can be determined directly from these sections, but truly three-dimensional properties such as connectivity of pores need three-dimensional analysis. In contrast to the case of a human brain, the anisotropies of microstructures in rocks are not typically known prior to cross sectioning, and so the optimal spacing of successive cross sections is unknown. Further, the cost of performing cross sectioning tends to lessen the number of sections taken and thereby increase the spacing between successive sections. Thus there is a problem of creating three-dimensional displays from a series of spaced parallel two-dimensional cross sections.
E. Keppel, Approximating Complex Surface by Triangularization of Contour Lines, 19 IBM J.Res.Dev. 2 (1975), formulated the problem of approximating the shape of a 3-D object from a series of sections as a combinatorial problem of graphs. His approach is stated as: Given polygonal contours on two sections, find a set of triangular patches that yield the optimal shape between two sections. A criterion for the optimal shape varies from the maximum volume (Keppel, 1975) to the minimum surface of Fuchs et al, Optimal Surface Reconstruction from Planar Contours, 20 Communications of the ACM 693 (1977), and locally minimized paths of Christiansen and Sederberg, Conversion of Complex Contour Line Definitions into Polygonal Element Mosaics, 12 Computer Graphics, ACM-SIGGRAPH 187 (1978). One of the earliest applications to geological problems was for a shape reconstruction of brachiopoda by Tipper, The Study of Geological Objects in Three Dimensions by the Computerized Reconstruction of Serial Sections, 84 Journal of Geology 476 (1976), and Tipper, A method and Fortran Program for the Computerized Reconstruction of Three-Dimensional Objects from Serial Sections, 3 Computers and Geosciences 579 (1977), although his algorithm was general for any triangular patch problem.
As pointed out by Ganapathy and Dennehy, A New General Triangularization Method for Planar Contours, 16 Computer Graphics, SIGGRAPH-ACM 69 (1982), the number of possible triangular patches increases as a function of factorials of the number of nodes in two polygons. Thus the strategy of the more recent work is, rather than approaching the problem from a general combinatorial aspect, to decompose contours using various criteria such as the parity of radial intersections (P. A. Dowd, in Earnshaw (Ed.), Fundamental Algorithms for Computer Graphics, Springer-Verlag, Berlin 1985), tolerance (Zyda et al, 11 Computers & Graphics 393, 1987), and span pairs (Sinclair et al, 13 Computers & Graphics 311, 1989).
In order for the triangular patch algorithm (e.g., Christiansen and Sederberg) to be practical, the number of vertices of a polygonal contour must not be too large, typically not more than a couple of hundred. As is obvious from the typical images shown in FIGS. 2a-b, the boundary has to be overly simplified for this method. But because a microscopic cross section of a rock specimen contains very detailed information on the boundary shape, the resolution of boundaries should be maintained for interpolation without further simplification of the shape. Thus the present invention is based on pixel (picture element) data of a digitized image, but not on the polygonal contour approximation.
The present invention provides interpolation on the pixel level. In some preferred embodiments the difference region between two regions from successive cross sections is skeletonized to form the boundary of an interpolation region of the two regions, and in other preferred embodiments multiple interpolation cross sections are constructed from relative distances within the difference region.